/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._67;

/**
 *
 * 给定两个二进制字符串，返回他们的和（用二进制表示）。
 *
 * 输入为非空字符串且只包含数字 1 和 0。
 *
 * 输入: a = "11", b = "1"
 * 输出: "100"
 *
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._67
 * @ClassName: AddBinary
 * @Author: linyaonan
 * @Date: 2019/10/21 17:31
 */
public class AddBinary {

    public String addBinary(String a, String b) {
        // 两个字符串输入不为空，并且输出值仅包含0，1
        // 判断较短的字符串，将该字符串作为循环字符串
        boolean isALong = a.length() >= b.length();
        // 找出长，短字符串
        String longStr = isALong ? a : b;
        String shortStr = isALong ? b : a;
        // 定义初始化索引
        int longIndex = longStr.length() - 1;
        int shortIndex = shortStr.length() - 1;
        StringBuilder buffer = new StringBuilder();
        for (; shortIndex >= 0;) {
            // 短字符
            String s = String.valueOf(shortStr.charAt(shortIndex));
            // 长字符
            String l = String.valueOf(longStr.charAt(longIndex));
            String addStr = addOneStr(s, l);
            buffer.append(addStr);
            longIndex--;
            shortIndex--;
        }
        for(; longIndex >= 0;longIndex--) {
            buffer.append(longStr.charAt(longIndex));
        }
        for (int i = 0; i < buffer.length() - 1; i++) {
            char c = buffer.charAt(i);
            if (c >= '2') {
                int v = (int) c % 2;
                // 本位取模
                buffer.replace(i, i+1, String.valueOf(v));
                String nextV = String.valueOf(buffer.charAt(i + 1));
                // 下位加一
                buffer.replace(i+1, i+2, addOneStr(nextV, "1"));
            }
        }

        char last = buffer.charAt(buffer.length() - 1);
        if (last >= '2') {
            int lastV = (int) last % 2;
            buffer.replace(buffer.length()-1, buffer.length(), String.valueOf(lastV));
            buffer.append("1");
        }
        return buffer.reverse().toString();
    }

    /**
     * 输入值，只能为 0， 1
     */
    private String addOneStr(String a, String b) {
        return String.valueOf(Integer.valueOf(a) + Integer.valueOf(b));
    }
}
